1. Field
The invention refers to a method for automatically evaluating the center line of an arbitrarily shaped object using, e.g., a digitized image of the object.
2. Related Art
Various methods have been used for automatic evaluation of objects and shapes, especially in automatic examination of objects during manufacturing. In such methods, an image of the object to be examined is taken by means of, e.g., high-dynamic range camera, an infrared camera, an x-ray camera, an ultra-sonic device, etc. The image is transferred to a calculating unit and is processed by means of image processing methods. Some automatic testing and evaluation procedures require the system to determine the centerline of the imaged object. The centerline is composed of interior points of the object, which extend along the lengthwise run of the object, and which are each positioned at the mid-distance to the boundaries of the object around the point, whether the investigation is done in two or three dimensions. The length of the centerline can represent the length of the object to be examined. Therefore, the evaluation of the centerline can be taken as an aid for solving various digital geometrical or topological problems, for example, in the course of measuring an object. Furthermore, the points of the centerline may contain information on the inner area of the object to be examined. Therefore, an automatic method for evaluating the centerline of an object is of substantial economic importance. Examples where the centerline evaluation may be useful include automatic evaluation of roads using, e.g., satellite images or stereo images from mobile mapping systems, centerline extraction of segmented blood vessels using, e.g., MRI images, inspection of weld seam in various robotic manufacturing, etc.
In connection with the industrial image processing, a method is already known with which the length of the centerline of an object, the so-called arch length, is estimated mathematically (“Industrial Image Processing”, Christian Demant, Bernd Streicher-Abel, Peter Waszkewitz, Berlin-Heidelberg; Springer, 1998). According to various methods of the prior art, the centerline of the object can be determined by a process generally referred to as skeletonizing or thinning of an object, according to which the object is progressively thinned by serially removing the outer pixels of the object until only the center pixels remain. The centerline is then represented by the collection of the remaining pixels (“Digital Image Processing”, Bernd Jähne, 4th edition, Berlin-Heidelberg, Springer, 1997). Although the characteristics of the various skeletonizing or thinning methods are very much different from each other, none of these methods provides an explicit and stable evaluation of the centerline of an object. The large variation in boundary conditions used for the skeletonizing of the object (breath and running path, continuous components, sensitivity to noise signals and convergence) cause substantial differences between the calculated one-pixel wide object and the actual centerline of the object to be evaluated.
According to other methods, the centerline of an object can be evaluated by scanning along its longitudinal direction. An example is illustrated in FIG. 1, wherein the broken arrow 105 depicts the scanning direction along object 100, having the scanning starting at the point marked “s” and ending at the point marked “e”. The scanning direction is basically defined as the direction in which the examination of the object and the calculation of the centerline proceed. At each examination position along the scanning direction, a line laying in a transverse, i.e., orthogonal, direction to the scanning direction is referred to as the detection direction. At each point along the scanning direction, the detection direction is evaluated to determine the two points along the detection direction that are at the two opposite extreme ends of the object 100 (for the case of a two dimensional examination). In FIG. 1, points a and b illustrate two points on the detection direction, wherein each point delimits the opposite boundary of the object 100 at that particular location in the scanning direction. The line 110 connects the two points a and b and is orthogonal to the scanning direction at that particular point along the scanning direction. The mid-distance between these two points defines a point 115 on the line 110, which is set to be a point of the centerline of object 100 at this particular location along the scanning direction. The collection of all of the mid-distances along the scanning direction are set to represent the centerline of the object 100.
This method dependents on the local shape and location of the object to be examined and, therefore, this method is rather elaborate since the detection method has to be programmed separately for each shape and orientation of the object to be examined. That is, if one superimposes a Cartesian space as shown in FIG. 1, it is evident that for each object the scanning direction needs be accurately defined at each examination point, and at each examination point the detection direction needs to be defined. Consequently, the automatic determination of the centerline requires a lot of processing, and even slight variation in the image quality or in defining the scanning and detection directions at each examination point leads to different determination of the centerline.
Furthermore, a so-called “ad-hoc-method” is known in which the preliminary segmentation and path calculation steps across the whole object to be examined are replaced such that the center line is calculated at each segment for the actual centerline location. This method is used, for example, for the automatic local route planning as it is used for the virtual endoscopy and the virtual colonoscopy (U.S. Ser. No. 10/322,326). However, this method fails in case, for example, a steep bend is present in the object to be examined.
A step-by-step method (DE 11 2004 000 128 B4) assists in evaluating the respective centerline point at each position by means of a cluster of the cross section area. For carrying out this method, it is, however, necessary to previously know the coordinate data set as well as the very first starting position of the object to be examined. Furthermore, this method requires a very elaborate procedure, the simplification of which would be advantageous in many technical applications in which, for example, the centerline of an object to be examined is formed as a non-crossing or non-contacting line.